package com.itheima.algorithm.backtracking;

import java.util.Arrays;

/**
 * (A卷,200分)- 最多几个直角三角形（Java & JS & Python）
 * 题目描述
 * 有N条线段，长度分别为a[1]-a[n]。
 * <p>
 * 现要求你计算这N条线段最多可以组合成几个直角三角形。
 * <p>
 * 每条线段只能使用一次，每个三角形包含三条线段。
 * <p>
 * 输入描述
 * 第一行输入一个正整数T（1<＝T<＝100），表示有T组测试数据.
 * <p>
 * 对于每组测试数据，接下来有T行，
 * <p>
 * 每行第一个正整数N，表示线段个数（3<＝N<＝20），接着是N个正整数，表示每条线段长度，（0<a[i]<100）。
 * <p>
 * 输出描述
 * 对于每组测试数据输出一行，每行包括一个整数，表示最多能组合的直角三角形个数
 * <p>
 * 用例
 * 输入	1
 * 7 3 4 5 6 5 12 13
 * 输出	2
 * 说明	可以组成2个直角三角形（3，4，5）、（5，12，13）
 */
public class MostRightTriangles {
    public static void main(String[] args) {
        /*// 处理输入
        Scanner in = new Scanner(System.in);
        // 处理输入
        int T = in.nextInt();
        for (int i = 0; i < T; i++) {
            int N = in.nextInt();
            int[] nums = new int[N];
            for (int j = 0; j < N; j++) {
                nums[j] = in.nextInt();
            }

            System.out.println(dfs(nums, 0));
        }*/

        Arrays.stream("7 3 4 5 6 5 12 13".split("\n"))
                .map(string -> Arrays.stream(string.split(" "))
                        .mapToInt(Integer::parseInt)
                        .toArray())
                .forEach(ints -> System.out.println(dfs(ints, 0)));
    }

    public static int dfs(int[] lines, int index) {
        Arrays.sort(lines);
        int maxVal = 0;
        int a;
        int b;
        int c;
        for (int i = index; i < lines.length - 2; i++) {
            a = lines[i];
            if (a == 0) {
                continue;
            }
            for (int j = i + 1; j < lines.length - 1; j++) {
                b = lines[j];
                if (b == 0) {
                    continue;
                }
                for (int k = j + 1; k < lines.length; k++) {
                    c = lines[k];
                    if (c == 0) {
                        continue;
                    }
                    if ((a * a + b * b) == c * c) {
                        lines[i] = 0;
                        lines[j] = 0;
                        lines[k] = 0;
                        maxVal = Math.max(maxVal, dfs(lines, i + 1) + 1);
                        lines[i] = a;
                        lines[j] = b;
                        lines[k] = c;
                    }
                }
            }
        }

        return maxVal;
    }
}